#include "DFA.h"
#include <iostream>
using std::cout;
using std::endl;
DFA::DFA()
{
    this->charset_cnt = 0;
    this->initial_state = 0;
    this->state_cnt = 0;
    this->final_state = {};
    this->trans = {};
}

DFA::DFA(size_t sc, size_t cc, map<pair<size_t, size_t>, size_t> tr, size_t is, set<size_t> ts)
{
    this->charset_cnt = cc;
    this->state_cnt = sc;
    this->trans = tr;
    this->initial_state = is;
    this->final_state = ts;
}

bool DFA::match(vector<size_t>string)
{
    size_t current_state = this->initial_state;
    for (auto& i : string)
    {
        if (!this->trans.count(std::make_pair(current_state, i)))
            return false;
        current_state = this->trans[std::make_pair(current_state, i)];
    }
    return this->final_state.count(current_state);
}

void DFA::print() const
{
    cout << "state_cnt  :  " << this->state_cnt << endl;
    cout << "charset_cnt  :  " << this->charset_cnt << endl;
    cout << "trans:" << endl;
    for (auto& i : this->trans)
        cout << i.first.first << "--" << i.first.second << "->" << i.second << endl;
    cout << "initial_state  :  " << this->initial_state << endl;
    cout << "final_state  :  ";
    for (auto& i : this->final_state)
        cout << i << "  ";
    cout << endl;
}

DFA* MinDFA(const DFA* dfa)
{
    if (dfa->final_state.size() == 0)return nullptr;
    size_t cnt = 0;
    vector<set<size_t>>states;
    map<size_t, size_t>master;
    for (const auto& i : dfa->final_state)
        master[i] = cnt;
    cnt++;
    states.push_back(dfa->final_state);
    set<size_t>s;
    for (size_t i = 0; i < dfa->state_cnt; i++)
        if (!dfa->final_state.count(i))
            s.insert(i), master[i] = cnt;
    cnt++;
    states.push_back(s);
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (size_t i = 0; i < states.size(); i++)
        {
            for (size_t c = 0; c < dfa->charset_cnt; c++)
            {
                map<size_t, set<size_t>>alpha;
                for (const auto& theta : states[i])
                    if (dfa->trans.count(std::make_pair(theta, c)))
                        alpha[master[dfa->trans.find(std::make_pair(theta, c))->second]].insert(theta);
                    else
                        alpha[size_t(-1)].insert(theta);
                if (alpha.size() > 1)
                {
                    flag = true;
                    states.erase(states.begin() + i);
                    i--;
                    for (const auto& m : alpha)
                    {
                        for (const auto& n : m.second)
                            master[n] = cnt;
                        cnt++;
                        states.push_back(m.second);
                    }
                    break;
                }
            }
        }
    }
    DFA* ret = new DFA();
    ret->charset_cnt = dfa->charset_cnt;
    master = map<size_t, size_t>();
    for (int i = 0; i < states.size(); i++)
    {
        if (states[i].empty())
        {
            states.erase(states.begin() + i);
            i--;
            continue;
        }
        for (const auto& c : states[i])
            master[c] = i;
    }
    ret->initial_state = master[dfa->initial_state];
    ret->state_cnt = states.size();
    for (const auto& i : dfa->final_state)
        ret->final_state.insert(master[i]);
    for (const auto& i : states)
    {
        if (i.size() == 0)continue;
        size_t s = *(i.begin());
        for (size_t c = 0; c < dfa->charset_cnt; c++)
        {
            if (dfa->trans.count(std::make_pair(s, c)))
            {
                ret->trans[std::make_pair(master[s], c)] = master[dfa->trans.find(std::make_pair(s, c))->second];
            }
        }
    }
    return ret;
}
